package com.issc.zq;

import java.util.Scanner;

/**
 * Created by Administrator on 2017/8/16.
 * 本程序实现：
 *              所有猴子按 1，2 ……… n 编号并按照顺序围成一圈，从第 k 个猴子起，由1开始报数，报到m时，该猴子就跳出圈外，
 *              下一只猴子再次由1开始报数，如此循环，直到圈内剩下一只猴子时，这只猴子就是大王。
 */
public class MonkeyKing {

    /*创建一个猴子的数组，数组的内容都为1.
                1表示猴子在圈里，等待继续报数
                0表示猴子已经跳出去了
     */
    public static int[] createMonkeyArry(int num){
        int [] monkeyArry = new int [num];
        for(int i = 0 ; i < num ; ++i){
            monkeyArry[i] =1;
        }
        return monkeyArry;
    }

    /*
    * 开始报数，每次报数为m的猴子，将其对应数组的内容置为0，并且下次遍历不会遍历内容为0的数组单元
    * */
    public static int selectMonkey(int [] monkeyArry,int m,int seat){
        int counter = 0;
        int sum = 0;
        int index;
        for(int i = seat ;i <= monkeyArry.length ; ++i) {      //此处的终止条件不能省略，千万不能省略。1、必须要有终止条件，int的函数要有返回值（不结束怎么返回）。2、使++i可以遍历到数组下表结束的下一个
            //实现将数组变为概念上的环形
            if(i == monkeyArry.length ){
                i = 0;
            }
            if (monkeyArry[i] != 0) {
                ++counter;                                  //每找到一个数组内容为1的，报一次数
                //报数为m的猴子，跳出圈外，数组位置置为0，并进行一次判断（是否只剩下一个猴子）
                if(m == counter ){
                    monkeyArry[i] = 0;
                    counter = 0;
                    index = verifyMonkeyKing(monkeyArry,sum);       //保存猴子大王的位置。为0需要继续找，不为0，直接返回其位置
                    if (index != 0) return index;
                }
            }
        }
        return  0;
    }
    /*找到猴子大王所在数组的位置*/
    public static int verifyMonkeyKing(int[] monkeyArry,int sum){
        //计算数组的总值（初始值为1，跳出猴子后，数组对应位置为0，）
        for(int j = 0 ; j < monkeyArry.length ; ++j){
            sum = sum + monkeyArry[j];
        }
        //如果sum为1，大王出现，找到大王位置并返回。
        if(sum == 1){
            for(int j = 0 ; j < monkeyArry.length ; ++j) {
                if(monkeyArry[j] == 1){
                    // System.out.println("第" + (j+1) + "只猴子就是辣个大王");        //
                    return  j + 1;
                }

            }
        }
        return 0;
    }

    public static void main(String [] args) {
        while (true) {
            System.out.println("请输入候选猴子的数量num：(num>=0)");
            Scanner input = new Scanner(System.in);
            int num = input.nextInt();

            System.out.println("请输入报数m：（报数为m的猴子出列,m>=0）");
            Scanner index = new Scanner(System.in);
            int m = index.nextInt();                        //报数到m跳出

            System.out.println("请输入开始报数猴子位置seat：（seat>=0）");
            Scanner intSeat = new Scanner(System.in);
            int seat = intSeat.nextInt();

            int outIndex;
            outIndex = selectMonkey(createMonkeyArry(num), m,seat-1);//传入生成数组，和报数m，以及开始报数的猴子位置。

            System.out.println("第" + outIndex + "只猴子就是辣个大王");
        }
    }
}
